<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-hemisu.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="hemisu">










<meta name="description" content="Just do...">
<meta name="keywords" content="web, 前端, 生活, 分享">
<meta property="og:type" content="website">
<meta property="og:title" content="何米酥`s Blog">
<meta property="og:url" content="http://www.hemisu.com/page/5/index.html">
<meta property="og:site_name" content="何米酥`s Blog">
<meta property="og:description" content="Just do...">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="何米酥`s Blog">
<meta name="twitter:description" content="Just do...">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://www.hemisu.com/page/5/">





  <title>何米酥`s Blog</title>
  








  <!-- Hotjar Tracking Code for www.hemisu.com -->
  <script>
      (function(h,o,t,j,a,r){
          h.hj=h.hj||function(){(h.hj.q=h.hj.q||[]).push(arguments)};
          h._hjSettings={hjid:1933736,hjsv:6};
          a=o.getElementsByTagName('head')[0];
          r=o.createElement('script');r.async=1;
          r.src=t+h._hjSettings.hjid+j+h._hjSettings.hjsv;
          a.appendChild(r);
      })(window,document,'https://static.hotjar.com/c/hotjar-','.js?sv=');
  </script>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">何米酥`s Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">EFE</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/03/05/269/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/03/05/269/" itemprop="url">PAT A1125 . Chain the Ropes (25)</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-05T13:27:09+00:00">
                2017-03-05
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given some segments of rope, you are supposed to chain them into one rope. Each time you may only fold two segments into loops and chain them into one piece, as shown by the figure. The resulting chain will be treated as another segment of rope and can be folded again. After each chaining, the lengths of the original two segments will be halved.</p>
<p>Your job is to make the longest possible rope out of N given segments.</p>
<p><strong>Input Specification:</strong></p>
<p>Each input file contains one test case. For each case, the first line gives a positive integer N (2 &lt;= N &lt;= 104). Then N positive integer lengths of the segments are given in the next line, separated by spaces. All the integers are no more than 104.</p>
<p><strong>Output Specification:</strong></p>
<p>For each case, print in a line the length of the longest possible rope that can be made by the given segments. The result must be rounded to the nearest integer that is no greater than the maximum length.</p>
<p><strong>Sample Input:</strong><br>8<br>10 15 12 3 4 13 1 15<br><strong>Sample Output:</strong><br>14<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;stdio.h&gt;</span><br><span class="line">#include &lt;iostream&gt;</span><br><span class="line">#include &lt;algorithm&gt;</span><br><span class="line">#include &lt;string.h&gt;</span><br><span class="line">#include &lt;string&gt;</span><br><span class="line">#include &lt;queue&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">int n;</span><br><span class="line">priority_queue&lt;double,vector&lt;double&gt;,greater&lt;double&gt;&gt; q;</span><br><span class="line">int main()&#123;</span><br><span class="line">  double a, b, temp;</span><br><span class="line">  scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">  for (int i=0; i&lt; n; i++)&#123;</span><br><span class="line">    scanf(&quot;%lf&quot;, &amp;temp);</span><br><span class="line">    q.push(temp);</span><br><span class="line">  &#125;</span><br><span class="line">  while(q.size() &gt; 1)&#123;</span><br><span class="line">    a = q.top();</span><br><span class="line">    q.pop();</span><br><span class="line">    b = q.top();</span><br><span class="line">    q.pop();</span><br><span class="line">    temp = (a + b)/2;</span><br><span class="line">    q.push(temp);</span><br><span class="line">  &#125;</span><br><span class="line">  printf(&quot;%d\n&quot;,(int)q.top());</span><br><span class="line">  return 0;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/03/05/267/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/03/05/267/" itemprop="url">PAT A1124 . Raffle for Weibo Followers (20)</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-05T13:25:00+00:00">
                2017-03-05
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>John got a full mark on PAT. He was so happy that he decided to hold a raffle（抽奖） for his followers on Weibo – that is, he would select winners from every N followers who forwarded his post, and give away gifts. Now you are supposed to help him generate the list of winners.</p>
<p><strong>Input Specification:</strong></p>
<p>Each input file contains one test case. For each case, the first line gives three positive integers M (&lt;= 1000), N and S, being the total number of forwards, the skip number of winners, and the index of the first winner (the indices start from 1). Then M lines follow, each gives the nickname (a nonempty string of no more than 20 characters, with no white space or return) of a follower who has forwarded John’s post.</p>
<p>Note: it is possible that someone would forward more than once, but no one can win more than once. Hence if the current candidate of a winner has won before, we must skip him/her and consider the next one.</p>
<p><strong>Output Specification:</strong></p>
<p>For each case, print the list of winners in the same order as in the input, each nickname occupies a line. If there is no winner yet, print “Keep going…” instead.</p>
<p><strong>Sample Input 1:</strong><br>9 3 2<br>Imgonnawin!<br>PickMe<br>PickMeMeMeee<br>LookHere<br>Imgonnawin!<br>TryAgainAgain<br>TryAgainAgain<br>Imgonnawin!<br>TryAgainAgain<br><strong>Sample Output 1:</strong><br>PickMe<br>Imgonnawin!<br>TryAgainAgain<br><strong>Sample Input 2:</strong><br>2 3 5<br>Imgonnawin!<br>PickMe<br><strong>Sample Output 2:</strong><br>Keep going…</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;stdio.h&gt;</span><br><span class="line">#include &lt;iostream&gt;</span><br><span class="line">#include &lt;algorithm&gt;</span><br><span class="line">#include &lt;string.h&gt;</span><br><span class="line">#include &lt;string&gt;</span><br><span class="line">#include &lt;queue&gt;</span><br><span class="line">#include &lt;set&gt;</span><br><span class="line">#include &lt;map&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">int m, n, s;</span><br><span class="line">string temp;</span><br><span class="line">vector&lt;string&gt; str;</span><br><span class="line">map&lt;string, int&gt; mp;</span><br><span class="line">int main()&#123;</span><br><span class="line">  //freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);</span><br><span class="line"></span><br><span class="line">  scanf(&quot;%d%d%d&quot;, &amp;m, &amp;n, &amp;s);</span><br><span class="line">  str.resize(m);</span><br><span class="line">  if(s&gt;m)&#123; printf(&quot;Keep going...\n&quot;); return 0;&#125;</span><br><span class="line">  for (int i = 0; i &lt; m; i++)&#123;</span><br><span class="line">    cin&gt;&gt;str[i];</span><br><span class="line">  &#125;</span><br><span class="line">  int t = s - 1;</span><br><span class="line">  while(t &lt; m)&#123;</span><br><span class="line">    if(mp[str[t]] != 1)&#123;</span><br><span class="line">      mp[str[t]] = 1;</span><br><span class="line">      cout&lt;&lt;str[t]&lt;&lt;endl;</span><br><span class="line">      t+= n;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">      t++;  </span><br><span class="line">    &#125;         </span><br><span class="line">  &#125;</span><br><span class="line">  return 0;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/03/02/260/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/03/02/260/" itemprop="url">PAT A1116 . Come on! Let's C (20)</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-02T22:35:00+00:00">
                2017-03-02
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>“Let’s C” is a popular and fun programming contest hosted by the College of Computer Science and Technology, Zhejiang University. Since the idea of the contest is for fun, the award rules are funny as the following: 0. The Champion will receive a “Mystery Award” (such as a BIG collection of students’ research papers…). 1. Those who ranked as a prime number will receive the best award – the Minions (小黄人)! 2. Everyone else will receive chocolates. Given the final ranklist and a sequence of contestant ID’s, you are supposed to tell the corresponding awards. Input Specification: Each input file contains one test case. For each case, the first line gives a positive integer N (&lt;=10000), the total number of contestants. Then N lines of the ranklist follow, each in order gives a contestant’s ID (a 4-digit number). After the ranklist, there is a positive integer K followed by K query ID’s. Output Specification: For each query, print in a line “ID: award” where the award is “Mystery Award”, or “Minion”, or “Chocolate”. If the ID is not in the ranklist, print “Are you kidding?” instead. If the ID has been checked before, print “ID: Checked”. Sample Input: 6 1111 6666 8888 1234 5555 0001 6 8888 0001 1111 2222 8888 2222 Sample Output: 8888: Minion 0001: Chocolate 1111: Mystery Award 2222: Are you kidding? 8888: Checked 2222: Are you kidding? #include &lt;stdio.h&gt;#include &lt;math.h&gt;#include &lt;string.h&gt;#include <algorithm>#include <iostream>#include <map>#include <vector>#include <queue>using namespace std; map &lt;int, string=””&gt;mp; bool isPrime(int v){ if (v &lt;= 1) { return false; } int sqr = (int)sqrt(1.0 * v); for (int i = 2; i &lt;= sqr; i++) { if (v % i == 0) { return false; } } return true; } int main(){ int n, temp, query; scanf(“%d”, &amp;n); for(int i = 1;i &lt;= n; i++){ scanf(“%d”, &amp;temp); if (i == 1) { mp[temp] = “Mystery Award”; }else if(isPrime(i)){ mp[temp] = “Minion”; }else{ mp[temp] = “Chocolate”; } } scanf(“%d”, &amp;query); for (int i = 0; i &lt; query; i++) { scanf(“%d”, &amp;temp); map&lt;int, string=””&gt;::iterator it = mp.find(temp); if (it != mp.end()) { printf(“%04d: “, temp); cout &lt;&lt; it-&gt;second&lt;&lt;/int,&gt;&lt;/int,&gt;</queue></vector></map></iostream></algorithm>&lt;/string.h&gt;&lt;/math.h&gt;&lt;/stdio.h&gt;</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/03/02/258/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/03/02/258/" itemprop="url">PAT A1123 . Is It a Complete AVL Tree (30)</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-02T21:29:00+00:00">
                2017-03-02
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.</p>
<p><img src="https://www.patest.cn/upload/mr_ohesevgnyny.jpg" alt="请输入图片描述"><br><img src="https://www.patest.cn/upload/mr_ohesfdbkaep.jpg" alt="请输入图片描述"><br><img src="https://www.patest.cn/upload/mr_oheseymzi13.jpg" alt="请输入图片描述"><br><img src="https://www.patest.cn/upload/mr_ohesfjddti2.jpg" alt="请输入图片描述"></p>
<p>Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains a positive integer N (&lt;= 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print “YES” if the tree is complete, or “NO” if not.</p>
<p>Sample Input 1:<br>5<br>88 70 61 63 65<br>Sample Output 1:<br>70 63 88 61 65<br>YES<br>Sample Input 2:<br>8<br>88 70 61 96 120 90 65 68<br>Sample Output 2:<br>88 65 96 61 70 90 120 68<br>NO<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;stdio.h&gt;</span><br><span class="line">#include &lt;algorithm&gt;</span><br><span class="line">#include &lt;vector&gt;</span><br><span class="line">#include &lt;queue&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">vector&lt;int&gt; layer;</span><br><span class="line"></span><br><span class="line">struct node&#123;</span><br><span class="line">    int v,height;</span><br><span class="line">    int order;</span><br><span class="line">    node *lchild,*rchild;</span><br><span class="line">&#125;;</span><br><span class="line">node* newNode(int v)&#123;</span><br><span class="line">    node* Node = new node;</span><br><span class="line">    Node-&gt;v = v;</span><br><span class="line">    Node-&gt;height = 1;</span><br><span class="line">    Node-&gt;lchild = Node-&gt;rchild = NULL;</span><br><span class="line">    return Node;</span><br><span class="line">&#125;</span><br><span class="line">int getHeight(node* root)&#123;</span><br><span class="line">    if(root == NULL) return 0;</span><br><span class="line">    return root-&gt;height;</span><br><span class="line">&#125;</span><br><span class="line">int getBalanceFactor(node* root)&#123;</span><br><span class="line">    return getHeight(root-&gt;lchild)-getHeight(root-&gt;rchild);</span><br><span class="line">&#125;</span><br><span class="line">void updateHeight(node* root)&#123;</span><br><span class="line">    root-&gt;height=max(getHeight(root-&gt;lchild),getHeight(root-&gt;rchild))+1;</span><br><span class="line">&#125;</span><br><span class="line">void L(node* &amp;root)&#123;</span><br><span class="line">    node* temp = root-&gt;rchild;</span><br><span class="line">    root-&gt;rchild = temp-&gt;lchild;</span><br><span class="line">    temp-&gt;lchild = root;</span><br><span class="line">    updateHeight(root);</span><br><span class="line">    updateHeight(temp);</span><br><span class="line">    root = temp;</span><br><span class="line">&#125;</span><br><span class="line">void R(node* &amp;root)&#123;</span><br><span class="line">    node* temp = root-&gt;lchild;</span><br><span class="line">    root-&gt;lchild = temp-&gt;rchild;</span><br><span class="line">    temp-&gt;rchild = root;</span><br><span class="line">    updateHeight(root);</span><br><span class="line">    updateHeight(temp);</span><br><span class="line">    root = temp;</span><br><span class="line">&#125;</span><br><span class="line">void insert(node* &amp;root,int v)&#123;</span><br><span class="line">    if(root == NULL)&#123;</span><br><span class="line">        root = newNode(v);</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    if(v &lt; root-&gt;v)&#123;</span><br><span class="line">        insert(root-&gt;lchild,v);</span><br><span class="line">        updateHeight(root);</span><br><span class="line">        if(getBalanceFactor(root) == 2)&#123;</span><br><span class="line">            if(getBalanceFactor(root-&gt;lchild) == 1)&#123;//LL</span><br><span class="line">                R(root);</span><br><span class="line">            &#125;</span><br><span class="line">            else if(getBalanceFactor(root-&gt;lchild) == -1)&#123;//LR</span><br><span class="line">                L(root-&gt;lchild);</span><br><span class="line">                R(root);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    else&#123;</span><br><span class="line">        insert(root-&gt;rchild,v);</span><br><span class="line">        updateHeight(root);</span><br><span class="line">        if(getBalanceFactor(root) == -2)&#123;</span><br><span class="line">            if(getBalanceFactor(root-&gt;rchild) == -1)&#123;//RR</span><br><span class="line">                L(root);</span><br><span class="line">            &#125;</span><br><span class="line">            else if(getBalanceFactor(root-&gt;rchild) == 1)&#123;//RL</span><br><span class="line">                R(root-&gt;rchild);</span><br><span class="line">                L(root);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">node *last = new node;</span><br><span class="line">void layerOrder(node* root,vector&lt;int&gt; &amp;vi)&#123;</span><br><span class="line">    queue&lt;node*&gt; q;</span><br><span class="line">    q.push(root);</span><br><span class="line">    root-&gt;order = 1;</span><br><span class="line">    while (!q.empty()) &#123;</span><br><span class="line">        node* now = q.front();</span><br><span class="line">        last = now;</span><br><span class="line">        q.pop();</span><br><span class="line">        vi.push_back(now-&gt;v);</span><br><span class="line">        if (now-&gt;lchild != NULL) &#123;</span><br><span class="line">            q.push(now-&gt;lchild);</span><br><span class="line">            now-&gt;lchild-&gt;order = 2 * now-&gt;order;</span><br><span class="line">        &#125;</span><br><span class="line">        if (now-&gt;rchild != NULL) &#123;</span><br><span class="line">            q.push(now-&gt;rchild);</span><br><span class="line">            now-&gt;rchild-&gt;order = 2 * now-&gt;order + 1;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, temp;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    node* root = NULL;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;temp);</span><br><span class="line">        insert(root, temp);</span><br><span class="line">    &#125;</span><br><span class="line">    layerOrder(root, layer);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, layer[i]);</span><br><span class="line">        if (i &lt; n - 1) printf(&quot; &quot;);</span><br><span class="line">        else printf(&quot;\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    if (last-&gt;order == n) &#123;</span><br><span class="line">        printf(&quot;YES\n&quot;);</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        printf(&quot;NO\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/03/02/257/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/03/02/257/" itemprop="url">PAT A1119 . Pre- and Post-order Traversals (30)</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-02T19:36:00+00:00">
                2017-03-02
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences, or preorder and inorder traversal sequences. However, if only the postorder and preorder traversal sequences are given, the corresponding tree may no longer be unique. Now given a pair of postorder and preorder traversal sequences, you are supposed to output the corresponding inorder traversal sequence of the tree. If the tree is not unique, simply output any one of them. Input Specification: Each input file contains one test case. For each case, the first line gives a positive integer N (&lt;=30), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space. Output Specification: For each test case, first printf in a line “Yes” if the tree is unique, or “No” if not. Then print in the next line the inorder traversal sequence of the corresponding binary tree. If the solution is not unique, any answer would do. It is guaranteed that at least one solution exists. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line. Sample Input 1: 7 1 2 3 4 6 7 5 2 6 7 4 5 3 1 Sample Output 1: Yes 2 1 6 4 7 3 5 Sample Input 2: 4 1 2 3 4 2 4 3 1 Sample Output 2: No 2 1 3 4 #include &lt;stdio.h&gt;#include <algorithm>#include <vector>using namespace std; vector <int>ans; int <em>pre, </em>post; bool uni = true;//true中序树唯一 struct node{ int data; node<em> left, </em> right; }; node <em>create(int preL, int preR, int postL, int postR){ if (preL &gt; preR) { return NULL; } node </em>root = new node; root-&gt;data = pre[preL]; root-&gt;left = root-&gt;right = NULL; if (preL == preR) { return root; } int k = 0; for (k = preL + 1; k &lt;= preR; k++) { if (pre[k] == post[postR - 1]) { break;//定位根节点的孩子结点在先序中的位置 } } if (k - preL &gt; 1) {//不是先序中的左孩子，唯一，确定是根的右孩子 int numLeft = (k - 1) - (preL + 1);//根的右孩子前面都是左子树 root-&gt;left = create(preL + 1, k - 1, postL, postL + numLeft); root-&gt;right = create(k, preR, postL + numLeft + 1, postR - 1); }else{//无法确定是左孩子还是右孩子 uni = false;//生成树不唯一 root-&gt;right = create(k, preR, postL, postR - 1);//作为右孩子 } return root; } void inOrder(node<em> root,vector<int>&amp; vi){ if (root == NULL) { return; } inOrder(root-&gt;left, vi); vi.push_back(root-&gt;data); inOrder(root-&gt;right, vi); } int main(){ int n = 0; vector <int>in; scanf(“%d”, &amp;n); pre = new int[n]; post = new int[n]; for (int i = 0; i &lt; n; i++) { scanf(“%d”, &amp;pre[i]); } for (int i = 0; i &lt; n; i++) { scanf(“%d”, &amp;post[i]); } node</int></int></em> root = create(0, n - 1, 0, n - 1); inOrder(root, in); if (uni) { printf(“Yes\n”); }else{ printf(“No\n”); } for (int i = 0; i &lt; in.size(); i++) { printf(“%d”, in[i]); if (i &lt; in.size() - 1) { printf(“ “); }else{ printf(“\n”); } } return 0; }</int></vector></algorithm>&lt;/stdio.h&gt;</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/03/02/255/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/03/02/255/" itemprop="url">PAT重点整理——二叉树生成</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-02T13:50:00+00:00">
                2017-03-02
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p><strong>树的生成</strong><br>中序序列可以与先序序列、后序序列、层序序列中的任意一个来构建唯一的二叉树。</p>
<p>先序+中序：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">node* create(int preL, int preR, int inL, int inR)&#123;</span><br><span class="line">    if (preL &gt; preR) &#123;</span><br><span class="line">        return NULL;</span><br><span class="line">    &#125;</span><br><span class="line">    node* root = new node;</span><br><span class="line">    root-&gt;data = pre[preL];</span><br><span class="line">    root-&gt;left = root-&gt;right = NULL;</span><br><span class="line">    int k;</span><br><span class="line">    for (k = inL; k &lt;= inR; k++) &#123;</span><br><span class="line">        if (root-&gt;data == in[k]) &#123;</span><br><span class="line">            break;//找到根节点</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int numLeft = k - inL;</span><br><span class="line">    root-&gt;left = create(preL + 1, preL + numLeft, inL, k - 1);</span><br><span class="line">    root-&gt;right = create(preL + numLeft, preR, k + 1, inR);</span><br><span class="line">    return root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>后序+中序：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">node* create(int postL, int postR, int inL, int inR)&#123;</span><br><span class="line">    if (postL &gt; postR) &#123;</span><br><span class="line">        return NULL;</span><br><span class="line">    &#125;</span><br><span class="line">    node* root = new node;</span><br><span class="line">    root-&gt;data = pre[postR];</span><br><span class="line">    root-&gt;left = root-&gt;right = NULL;</span><br><span class="line">    int k;</span><br><span class="line">    for (k = inL; k &lt;= inR; k++) &#123;</span><br><span class="line">        if (root-&gt;data == in[k]) &#123;</span><br><span class="line">            break;//找到根节点</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int numLeft = k - inL;</span><br><span class="line">    root-&gt;left = create(postL, postL + numLeft - 1, inL, k - 1);</span><br><span class="line">    root-&gt;right = create(postL + numLeft, postR - 1, k + 1, inR);</span><br><span class="line">    return root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>层次+中序：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">node* create(vector&lt;int&gt;layer, int inL, int inR)&#123;</span><br><span class="line">    if(layer.size() == 0)&#123;</span><br><span class="line">        return NULL;</span><br><span class="line">    &#125;</span><br><span class="line">    node* root = new node;</span><br><span class="line">    root-&gt;data = layer[0];</span><br><span class="line">    int k;</span><br><span class="line">    for (k = inL; k &lt;= inR; k++) &#123;</span><br><span class="line">        if (root-&gt;data == in[k]) &#123;</span><br><span class="line">            break;//找到根结点</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    vector&lt;int&gt; leftLayer;</span><br><span class="line">    vector&lt;int&gt; rightLayer;</span><br><span class="line">    for (int i = 0; i &lt; layer.size(); i++) &#123;//先从layer里找，因为顺序决定谁是根节点</span><br><span class="line">        bool isLeft = false;</span><br><span class="line">        for (int j = inL; j &lt; k; j++) &#123;</span><br><span class="line">            if (layer[i] == in[j]) &#123;//在中序的左边找到</span><br><span class="line">                isLeft = true;//是左子树上的点</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        if (isLeft) leftLayer.push_back(layer[i]);</span><br><span class="line">        else rightLayer.push_back(layer[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    root-&gt;left = create(leftLayer, inL, k - 1);</span><br><span class="line">    root-&gt;left = create(rightLayer, k + 1, inR);</span><br><span class="line">    return root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/03/02/254/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/03/02/254/" itemprop="url">3.1模拟题 problem4 上帝视角</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-02T13:39:54+00:00">
                2017-03-02
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>题目描述<br>给一棵二叉树的层序遍历序列和中序遍历序列，求这棵二叉树的先序遍历序列和后序遍历序列，并给出从右往左、从右上往左下、从上往下分别能看到的结点个数。注意，此处均把二叉树的每条边都设置为等长，角度为45度，因此结点可能在视觉上重叠。所谓从右往左看是指，对同一层的结点，右边的结点会挡住左边的结点，这样同一层结点就只能看到最右边的那一个；同样的，从右上往左下看是指，右上角的结点会挡住左下角45度的结点；从上往下看是指，对同一竖直位置来说，只能看到最上方的结点。</p>
<p>例如对下图来说，从右往左能看到3个结点，从右上往左下能看到3个结点，从上往下能看到5个结点。</p>
<p><img src="http://www.codeup.cn/upload/201603/image/D.png" alt="请输入图片描述"></p>
<p>输入<br>每个输入文件中一组数据。</p>
<p>第一行一个正整数N（1&lt;=N&lt;=30），代表二叉树的结点个数（结点编号为1~N）。</p>
<p>接下来两行，每行N个正整数，分别代表二叉树的层序遍历序列和中序遍历序列。数据保证序列中1~N的每个数出现且只出现一次。</p>
<p>输出<br>先输出两行，每行N个正整数，分别代表二叉树的先序遍历序列和后序遍历序列。</p>
<p>接下来分三行输出从右往左、从右上往左下、从上往下分别能看到的结点个数。</p>
<p>每行末尾均不允许输出多余的空格。</p>
<p>样例输入<br>7<br>1 2 3 4 5 6 7<br>4 2 5 1 6 3 7<br>样例输出<br>1 2 4 5 3 6 7<br>4 5 2 6 7 3 1<br>3<br>3<br>5<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;cstdio&gt;</span><br><span class="line">#include &lt;cmath&gt;</span><br><span class="line">#include &lt;cstring&gt;</span><br><span class="line">#include &lt;vector&gt;</span><br><span class="line">#include &lt;queue&gt;</span><br><span class="line">#include &lt;algorithm&gt;</span><br><span class="line">#include &lt;map&gt;</span><br><span class="line">#include &lt;stack&gt;</span><br><span class="line">#include &lt;ctype.h&gt;</span><br><span class="line">#include &lt;iostream&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">int  in[50], la[50];</span><br><span class="line">int n;</span><br><span class="line">vector&lt;int&gt; layervec, prevec, postvec;</span><br><span class="line">struct node&#123;</span><br><span class="line">    int data,layer;</span><br><span class="line">    node *left, *right;</span><br><span class="line">    node(node *_left = NULL, node *_right = NULL )&#123;</span><br><span class="line">        left = _left;//初始化</span><br><span class="line">        right = _right;//初始化</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line">node* createTree(vector&lt;int&gt; layer, int inL, int inR)&#123;</span><br><span class="line">    if (layer.size() == 0) &#123;//层次遍历为空，返回空地址</span><br><span class="line">        return NULL;</span><br><span class="line">    &#125;</span><br><span class="line">    node* root = new node;</span><br><span class="line">    root-&gt;data = layer[0];//层次向量中第一个为根节点</span><br><span class="line">    int k;</span><br><span class="line">    for (k = inL; k &lt;= inR; k++) &#123;</span><br><span class="line">        if (layer[0] == in[k]) &#123;//在中序遍历中找到根节点</span><br><span class="line">            break;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    vector&lt;int&gt; layerLeft;</span><br><span class="line">    vector&lt;int&gt; layerRight;</span><br><span class="line">    for (int i = 1; i &lt; layer.size(); i++) &#123;//在层次向量中枚举根节点左侧</span><br><span class="line">        bool isLeft = false;</span><br><span class="line">        for (int j = inL; j &lt; k; j++) &#123;</span><br><span class="line">            if (layer[i] == in[j]) &#123;</span><br><span class="line">                isLeft = true;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        if (isLeft) &#123;//找到一个按顺序放入，顺序在前的为根节点</span><br><span class="line">            layerLeft.push_back(layer[i]);</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            layerRight.push_back(layer[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    root-&gt;left = createTree(layerLeft, inL, k - 1);</span><br><span class="line">    root-&gt;right = createTree(layerRight, k + 1, inR);</span><br><span class="line">    return root;</span><br><span class="line">&#125;</span><br><span class="line">void preOrder(node *root, vector&lt;int&gt; &amp;vi)&#123;</span><br><span class="line">    if (root == NULL) &#123;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    vi.push_back(root-&gt;data);</span><br><span class="line">    preOrder(root-&gt;left, vi);</span><br><span class="line">    preOrder(root-&gt;right, vi);</span><br><span class="line">&#125;</span><br><span class="line">void postOrder(node *root, vector&lt;int&gt; &amp;vi)&#123;</span><br><span class="line">    if (root == NULL) &#123;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    postOrder(root-&gt;left, vi);</span><br><span class="line">    postOrder(root-&gt;right, vi);</span><br><span class="line">    vi.push_back(root-&gt;data);</span><br><span class="line">&#125;</span><br><span class="line">int maxlep = 0;</span><br><span class="line">void dfs(node* root, int ldep)&#123;</span><br><span class="line">    maxlep = max(maxlep, ldep);</span><br><span class="line">    if (root == NULL) &#123;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    if(root-&gt;left)dfs(root-&gt;left, ldep);</span><br><span class="line">    if(root-&gt;right)dfs(root-&gt;right, ldep + 1);</span><br><span class="line">    return;</span><br><span class="line">&#125;</span><br><span class="line">int minleaf = 0, maxleaf = 0;</span><br><span class="line">void dfs1(node* root, int ldep)&#123;</span><br><span class="line">    minleaf = min(minleaf, ldep);</span><br><span class="line">    maxleaf = max(maxleaf, ldep);</span><br><span class="line">    if (root == NULL) &#123;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    if(root-&gt;left)dfs1(root-&gt;left, ldep - 1);</span><br><span class="line">    if(root-&gt;right)dfs1(root-&gt;right, ldep + 1);</span><br><span class="line">    return;</span><br><span class="line">&#125;</span><br><span class="line">int layerOrder(node*root)&#123;//返回层数</span><br><span class="line">    queue&lt;node*&gt; q;</span><br><span class="line">    q.push(root);</span><br><span class="line">    root-&gt;layer = 1;</span><br><span class="line">    int maxlayer = 0;</span><br><span class="line">    while (!q.empty()) &#123;</span><br><span class="line">        node* now = q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        maxlayer = max(now-&gt;layer, maxlayer);</span><br><span class="line">        if (now-&gt;left != NULL) &#123;</span><br><span class="line">            now-&gt;left-&gt;layer = now-&gt;layer + 1;</span><br><span class="line">            q.push(now-&gt;left);</span><br><span class="line">        &#125;</span><br><span class="line">        if (now-&gt;right != NULL) &#123;</span><br><span class="line">            now-&gt;right-&gt;layer = now-&gt;layer + 1;</span><br><span class="line">            q.push(now-&gt;right);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    return maxlayer;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;//layer</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;la[i]);</span><br><span class="line">        layervec.push_back(la[i]);//入向量</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;//in</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;in[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    node *root = new node;</span><br><span class="line">    root = createTree(layervec, 0, n - 1);</span><br><span class="line">    preOrder(root,prevec);</span><br><span class="line">    postOrder(root,postvec);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        printf(&quot;%d&quot;,prevec[i]);</span><br><span class="line">        if (i &lt; n - 1) &#123;</span><br><span class="line">            printf(&quot; &quot;);</span><br><span class="line">        &#125;else printf(&quot;\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        printf(&quot;%d&quot;,postvec[i]);</span><br><span class="line">        if (i &lt; n - 1) &#123;</span><br><span class="line">            printf(&quot; &quot;);</span><br><span class="line">        &#125;else printf(&quot;\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    dfs(root, 0);//从右上往左下看</span><br><span class="line">    dfs1(root, 0);//从上往下看</span><br><span class="line">    printf(&quot;%d\n&quot;, layerOrder(root));</span><br><span class="line">    printf(&quot;%d\n&quot;, maxlep + 1);</span><br><span class="line">    printf(&quot;%d\n&quot;, abs(minleaf) + maxleaf + 1);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/03/02/252/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/03/02/252/" itemprop="url">3.1模拟题 problem2 万妖穴</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-02T11:08:00+00:00">
                2017-03-02
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p><strong>题目描述</strong><br>“万妖穴中有若干小穴，每处小穴中皆有一只恶妖。小穴外设有封印，汝需消灭指定几处小穴中的恶妖方能解除该小穴封印，进而消灭穴中恶妖。”</p>
<p>“此处石壁所刻便是万妖穴中各穴的封印解除关系。”</p>
<p>“万妖穴中或有部分小穴未设封印，汝可以此作为突破口。”</p>
<p>“吾将根据石壁所示，将各穴消灭顺序给予汝，汝自珍重。”</p>
<p><strong>输入</strong><br>每个输入文件中一组数据。</p>
<p>第一行两个正整数N、M（1&lt;=N&lt;=1000，0&lt;=M&lt;=N*(N-1)），表示万妖穴中小穴的个数及封印解除关系的条数。</p>
<p>接下来M行，每行两个整数a、b，表示小穴b封印的解除依赖于消灭小穴a中的恶妖。假设N处小穴的编号分别是0~N-1。数据保证a不等于b，且每组封印解除关系a b最多出现一次。</p>
<p><strong>输出</strong><br>如果能够消灭所有小穴，那么输出一行YES，并在第二行给出用空格隔开的N处小穴的消灭顺序（此处规定，总是消灭当前能消灭的编号最小的小穴）；如果不能消灭所有小穴，那么输出一行NO，并在第二行给出无法解除封印的小穴个数。行末均不允许输出多余的空格。</p>
<p>样例输入和输出那里贴不了多个case（提交的程序会强行测试sample），所以直接放这里吧<br><strong>input:</strong></p>
<pre><code>// case 1
3 3
0 1
0 2
2 1
// case 2
4 5
0 1
0 2
0 3
2 1
1 2
</code></pre><p><strong>output:</strong></p>
<pre><code>// case 1
YES
0 2 1
// case 2
NO
2
</code></pre><p>程序如下：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line">const int MAXV = 1010;</span><br><span class="line">int n, m, inDegree[MAXV];</span><br><span class="line">vector&lt;int&gt; G[MAXV],Q;</span><br><span class="line">int topologicalSort()&#123;</span><br><span class="line">    int num = 0;</span><br><span class="line">    priority_queue&lt;int,vector&lt;int&gt;,greater&lt;int&gt;&gt; q;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        if (inDegree[i] == 0) &#123;</span><br><span class="line">            q.push(i);//入度为0入队列</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    while (!q.empty()) &#123;</span><br><span class="line">        int u = q.top();</span><br><span class="line">        Q.push_back(u);</span><br><span class="line">        q.pop();</span><br><span class="line">        for (int i = 0; i &lt; G[u].size(); i++) &#123;</span><br><span class="line">            int v = G[u][i];</span><br><span class="line">            inDegree[v]--;//入度减少</span><br><span class="line">            if (inDegree[v] == 0) &#123;</span><br><span class="line">                q.push(v);//入度为0，加入队列</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        num++;</span><br><span class="line">    &#125;</span><br><span class="line">    return num;//返回拓扑结点个数</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d&quot;,&amp;n, &amp;m);</span><br><span class="line">    memset(inDegree, 0, sizeof(inDegree));//初始化</span><br><span class="line">    int u, v;</span><br><span class="line">    for (int i = 0 ; i &lt; m; i++) &#123;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;u, &amp;v);</span><br><span class="line">        G[u].push_back(v);</span><br><span class="line">        inDegree[v]++;//入度++</span><br><span class="line">    &#125;</span><br><span class="line">    int topological = topologicalSort();</span><br><span class="line">    if (topological == n) &#123;//封印解除！</span><br><span class="line">        printf(&quot;YES\n&quot;);</span><br><span class="line">        for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">            printf(&quot;%d&quot;, Q[i]);</span><br><span class="line">            if (i &lt; n - 1) &#123;</span><br><span class="line">                printf(&quot; &quot;);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        printf(&quot;NO\n%d\n&quot;, n - topological);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>题目中要求『此处规定，总是消灭当前能消灭的编号最小的小穴』<br>所以采用优先队列<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">priority_queue&lt;int, vector&lt;int&gt;, greater&lt;int&gt;&gt; q;</span><br></pre></td></tr></table></figure></p>
<p>下面给出一组测试数据<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">//input</span><br><span class="line"></span><br><span class="line">     6 5</span><br><span class="line">     0 1</span><br><span class="line">     0 2</span><br><span class="line">     1 5</span><br><span class="line">     1 3</span><br><span class="line">     1 4</span><br><span class="line"></span><br><span class="line">//output</span><br><span class="line"></span><br><span class="line">    YES</span><br><span class="line">    0 1 2 3 4 5</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/03/02/251/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/03/02/251/" itemprop="url">3.1模拟题 problem3 某计算器的超电磁炮</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-02T10:58:06+00:00">
                2017-03-02
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>题目描述<br>输入由非负整数、+、-、*、/、(、)组成的计算表达式，计算该表达式的值。</p>
<p>输入<br>每个输入文件中一组数据。</p>
<p>输入只有一行，不超过200个字符，其中不存在空格。数据保证表达式一定合法，且所有的整数都不小于0、不大于1024。中间结果保证不超过15位有效数位精度。</p>
<p>输出<br>输出一行，即表达式的值，结果精度保留小数点后2位。</p>
<p>样例输入<br>3+(12/(2*2+1))<br>样例输出<br>5.40<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;cstdio&gt;</span><br><span class="line">#include &lt;cmath&gt;</span><br><span class="line">#include &lt;cstring&gt;</span><br><span class="line">#include &lt;vector&gt;</span><br><span class="line">#include &lt;queue&gt;</span><br><span class="line">#include &lt;algorithm&gt;</span><br><span class="line">#include &lt;map&gt;</span><br><span class="line">#include &lt;stack&gt;</span><br><span class="line">#include &lt;ctype.h&gt;</span><br><span class="line">#include &lt;iostream&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">struct node&#123;</span><br><span class="line">    double num;</span><br><span class="line">    char op;</span><br><span class="line">    bool flag;</span><br><span class="line">&#125;;</span><br><span class="line">string str;</span><br><span class="line">stack&lt;node&gt; s;//操作符栈</span><br><span class="line">queue&lt;node&gt; q;//后缀表达式列</span><br><span class="line">map&lt;char, int&gt; op;</span><br><span class="line">void change()&#123;</span><br><span class="line">    double num;</span><br><span class="line">    node temp;</span><br><span class="line">    for (int i = 0; i &lt; str.length(); ) &#123;</span><br><span class="line">        if (isdigit(str[i])) &#123;</span><br><span class="line">            temp.flag = true;//是数字</span><br><span class="line">            temp.num = str[i++] - &apos;0&apos;;</span><br><span class="line">            while (i &lt; str.length() &amp;&amp; isdigit(str[i])) &#123;</span><br><span class="line">                temp.num = temp.num * 10 + str[i] - &apos;0&apos;;</span><br><span class="line">                i++;</span><br><span class="line">            &#125;</span><br><span class="line">            q.push(temp);</span><br><span class="line">        &#125;else if(str[i] == &apos;(&apos;)&#123;</span><br><span class="line">            temp.op = str[i];</span><br><span class="line">            s.push(temp);</span><br><span class="line">            i++;</span><br><span class="line">        &#125;else if(str[i] == &apos;)&apos;)&#123;</span><br><span class="line">            while (!s.empty() &amp;&amp; s.top().op != &apos;(&apos;) &#123;</span><br><span class="line">                q.push(s.top());</span><br><span class="line">                s.pop();</span><br><span class="line">            &#125;</span><br><span class="line">            s.pop();</span><br><span class="line">            i++;</span><br><span class="line">        &#125;else&#123;//是操作符</span><br><span class="line">            temp.flag = false;</span><br><span class="line">            while (!s.empty() &amp;&amp; op[s.top().op] &gt;= op[str[i]]) &#123;</span><br><span class="line">                q.push(s.top());</span><br><span class="line">                s.pop();</span><br><span class="line">            &#125;</span><br><span class="line">            temp.op = str[i];</span><br><span class="line">            s.push(temp);</span><br><span class="line">            i++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    while (!s.empty()) &#123;</span><br><span class="line">        q.push(s.top());</span><br><span class="line">        s.pop();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">double cal()&#123;</span><br><span class="line">    double temp1, temp2;</span><br><span class="line">    node cur, temp;</span><br><span class="line">    while (!q.empty()) &#123;</span><br><span class="line">        cur = q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        if (cur.flag == true) &#123;//是数字</span><br><span class="line">            s.push(cur);</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            temp2 = s.top().num;</span><br><span class="line">            s.pop();</span><br><span class="line">            temp1 = s.top().num;</span><br><span class="line">            s.pop();</span><br><span class="line">            temp.flag = true;</span><br><span class="line">            if (cur.op == &apos;+&apos;) &#123;</span><br><span class="line">                temp.num = temp1 + temp2;</span><br><span class="line">            &#125;else if(cur.op == &apos;-&apos;)&#123;</span><br><span class="line">                temp.num = temp1 - temp2;</span><br><span class="line">            &#125;else if(cur.op == &apos;*&apos;)&#123;</span><br><span class="line">                temp.num = temp1 * temp2;</span><br><span class="line">            &#125;else if(cur.op == &apos;/&apos;)&#123;</span><br><span class="line">                temp.num = temp1 / temp2;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return s.top().num;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    op[&apos;(&apos;] = op[&apos;)&apos;] = 0;</span><br><span class="line">    op[&apos;+&apos;] = op[&apos;-&apos;] = 1;</span><br><span class="line">    op[&apos;*&apos;] = op[&apos;/&apos;] = 2;</span><br><span class="line">    getline(cin, str);</span><br><span class="line">    change();</span><br><span class="line">    printf(&quot;%.2f\n&quot;,cal());</span><br><span class="line"></span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/03/01/248/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/03/01/248/" itemprop="url">2.28模拟题 problem4 调查黑暗气息</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-03-01T13:00:00+00:00">
                2017-03-01
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>在数码世界中有一个叫做“Radiation Zone”的区域，里面荒无人烟，仿佛遗迹一般。在这个区域中有N个城市（假设编号为从0到N-1），每个城市中都有一定数量的辐能。有M条已知长度的道路连接它们，每条道路都可以双向来往。</p>
<p>近期这个区域似有黑暗气息蛰伏，国王Shoutmon派出调查队前来调查这个区域中的城市。调查队的飞船降落在S号城市。由于飞船降落时气流不稳定，因此产生了辐能波，导致以S号城市为中心的L层以内（假设S号城市为最内层，记为第0层）的城市的辐能都会上升（只上升一次），上升的数值为 “城市的当前辐能乘以百分比p”的向上取整。其中百分比p在S号城市时为100%，且每向外扩散一层，百分比降低100%/L（例如，如果L为5，那么第0层（即S号城市）为100%，第1层为80%，第2层为60%，第3层为40%，第4层为20%，其中百分比均为浮点数）。所谓第X层是指，连接某城市与S号城市的最少数量的道路数，例如下图是一个例子，图中的数字为其层号。</p>
<p><img src="http://shoutmon.qiniudn.com/pic.png" alt="图片"></p>
<p>之后调查队需要前往T号城市调查。为了顺便清除城市中的辐能，他们准备了一个容量为K的辐能吸收器。辐能吸收器可以自动吸收城市中的辐能，且满容量时会自动将容器内的所有辐能都燃烧完毕，以继续吸收辐能。假设调查队总是把城市（含S号和T号城市）中的辐能吸收完毕。</p>
<p>为了节省体力，调查队希望选择一条长度最短的路径前往T号城市；如果这样的路径有多条，那么从中选择到达T号城市时辐能吸收器内当前辐能最大的路径；如果这样的路径仍然有多条，那么从中选择路径后半段的城市的辐能之和最小的路径（所谓后半段是指，如果路径上有m个城市，那么后m/2个城市（含T号城市）是后半段的城市。例如，如果路径上有7个城市，那么路径的后3个城市（除法为向下取整）为后半段的城市）。数据保证这样的路径一定唯一。</p>
<p>输入<br>每个输入文件中一组数据。</p>
<p>第一行六个整数N、M、L、K、S、T（2&lt;=N&lt;=500, M&lt;=N*(N-1)/2, 1&lt;=L&lt;=500, 2&lt;=K&lt;=100, S != T），分别代表城市个数、道路条数、辐能上升的层数、辐能吸收器的容量、起点城市编号、终点城市编号。</p>
<p>接下来一行有N个正整数，分别给出N个城市的初始辐能（均为不超过100的正整数）。</p>
<p>接下来M行，每行三个数字u、v、w，代表一条道路，其中u和v为道路的两个端点城市编号，w为道路的长度（w为不超过1000的正整数）。数据保证u不等于v，且相同的无序对(u,v)只出现一次。</p>
<p>输出<br>如果从S号城市不能到达T号城市，那么只输出-1。</p>
<p>如果从S号城市能到达T号城市，那么输出两行：</p>
<p>第一行输出四个整数， 即S号城市到T号城市的最短距离的路径条数（数据保证不超过100000条）、S号城市到T号城市的最短距离、通过最终选择的路径到达T号城市时辐能吸收器内的当前辐能、最终选择的路径的后半段城市的辐能之和。</p>
<p>第二行输出最终选择的路径，路径上的城市之间用-&gt;隔开。</p>
<p>样例输入<br>7 8 1 7 0 6<br>20 10 10 6 8 13 5<br>0 1 1<br>0 2 1<br>1 3 1<br>2 4 1<br>2 5 1<br>3 6 1<br>4 6 1<br>5 6 1<br>样例输出<br>3 3 5 11<br>0-&gt;1-&gt;3-&gt;6<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">#include &lt;cstdio&gt;</span><br><span class="line">#include &lt;cmath&gt;</span><br><span class="line">#include &lt;cstring&gt;</span><br><span class="line">#include &lt;vector&gt;</span><br><span class="line">#include &lt;queue&gt;</span><br><span class="line">#include &lt;algorithm&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">//N、M、L、K、S、T（2&lt;=N&lt;=500, M&lt;=N*(N-1)/2, 1&lt;=L&lt;=500, 2&lt;=K&lt;=100, S != T），分别代表城市个数、道路条数、辐能上升的层数、辐能吸收器的容量、起点城市编号、终点城市编号</span><br><span class="line">const int maxn = 510;</span><br><span class="line">const int INF = 1000000000;</span><br><span class="line">int n, m, l, k, s, t;</span><br><span class="line">int weight[maxn], G[maxn][maxn], d[maxn];</span><br><span class="line">int numPath = 0, remainK = -1, halfSumK = INF;</span><br><span class="line">bool inq[maxn] = &#123;false&#125;, vis[maxn] = &#123;false&#125;;</span><br><span class="line">vector&lt;int&gt; tempPath, path;</span><br><span class="line">vector&lt;int&gt; pre[maxn];</span><br><span class="line">struct node&#123;</span><br><span class="line">    int layer;//层数</span><br><span class="line">    int id;</span><br><span class="line">&#125;;</span><br><span class="line">void init()&#123;</span><br><span class="line">    fill(G[0], G[0]+ maxn * maxn, INF);</span><br><span class="line">    numPath = 0;</span><br><span class="line">    remainK = -1;</span><br><span class="line">    halfSumK = INF;</span><br><span class="line">    memset(vis, false, sizeof(vis));</span><br><span class="line">    memset(inq, false, sizeof(inq));</span><br><span class="line">    for (int i = 0; i &lt; maxn; i++) &#123;</span><br><span class="line">        pre[i].clear();</span><br><span class="line">    &#125;</span><br><span class="line">    tempPath.clear();</span><br><span class="line">    path.clear();</span><br><span class="line">&#125;</span><br><span class="line">void DFS(int v)&#123;</span><br><span class="line">    if (v == s) &#123;</span><br><span class="line">        tempPath.push_back(v);</span><br><span class="line">        numPath++;</span><br><span class="line">        int tempW = 0, temphalfSumK = 0;</span><br><span class="line">        for (int i = 0; i &lt; (int)tempPath.size() / 2; i++) &#123;</span><br><span class="line">            int id = tempPath[i];</span><br><span class="line">            tempW += weight[id];</span><br><span class="line">            temphalfSumK += weight[id];</span><br><span class="line">        &#125;</span><br><span class="line">        for (int i = (int)tempPath.size() / 2; i &lt; tempPath.size(); i++) &#123;</span><br><span class="line">            int id = tempPath[i];</span><br><span class="line">            tempW += weight[id];</span><br><span class="line">        &#125;</span><br><span class="line">        if (tempW % k &gt; remainK) &#123;</span><br><span class="line">            remainK = tempW % k;</span><br><span class="line">            halfSumK = temphalfSumK;</span><br><span class="line">            path = tempPath;</span><br><span class="line">        &#125;else if(tempW % k == remainK )&#123;</span><br><span class="line">            if (temphalfSumK &lt; halfSumK) &#123;</span><br><span class="line">                halfSumK = temphalfSumK;</span><br><span class="line">                path = tempPath;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        tempPath.pop_back();</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    tempPath.push_back(v);</span><br><span class="line">    for (int i = 0; i &lt; pre[v].size(); i++) &#123;</span><br><span class="line">        DFS(pre[v][i]);</span><br><span class="line">    &#125;</span><br><span class="line">    tempPath.pop_back();</span><br><span class="line">&#125;</span><br><span class="line">void Dijstra(int s)&#123;</span><br><span class="line">    fill(d, d + maxn, INF);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        pre[i].push_back(i);//初始化路径</span><br><span class="line">    &#125;</span><br><span class="line">    d[s] = 0;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        int u = -1, MIN = INF;</span><br><span class="line">        for (int j = 0; j &lt; n; j++) &#123;</span><br><span class="line">            if (vis[j] == false &amp;&amp; d[j] &lt; MIN) &#123;</span><br><span class="line">                u = j;</span><br><span class="line">                MIN = d[j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        if (u == -1) return;</span><br><span class="line">        vis[u] = true;</span><br><span class="line">        for (int v = 0; v &lt; n; v++) &#123;</span><br><span class="line">            if (vis[v] == false &amp;&amp; G[u][v] != INF) &#123;</span><br><span class="line">                if (d[u] + G[u][v] &lt; d[v] ) &#123;</span><br><span class="line">                    d[v] = d[u] + G[u][v];</span><br><span class="line">                    pre[v].clear();</span><br><span class="line">                    pre[v].push_back(u);</span><br><span class="line">                &#125;else if(d[u] + G[u][v] == d[v])&#123;</span><br><span class="line">                    pre[v].push_back(u);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">void BFS(int s)&#123;//BFS解决污染扩散问题</span><br><span class="line">    node start;</span><br><span class="line">    start.id = s;</span><br><span class="line">    start.layer = 0;</span><br><span class="line">    queue&lt;node&gt; q;</span><br><span class="line">    q.push(start);</span><br><span class="line">    inq[start.id] = true;</span><br><span class="line">    while (!q.empty()) &#123;</span><br><span class="line">        node now = q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        int u = now.id;</span><br><span class="line">        if (now.layer &lt; l) &#123;</span><br><span class="line">            weight[u] += (int)(ceil(weight[u] * 1.0 * (l - now.layer) / l ) + 0.5);</span><br><span class="line">        &#125;</span><br><span class="line">        for (int v = 0; v &lt; n; v++) &#123;</span><br><span class="line">            if (inq[v] == false &amp;&amp; G[u][v] != INF) &#123;</span><br><span class="line">                node next;</span><br><span class="line">                next.id = v;</span><br><span class="line">                next.layer = now.layer + 1;</span><br><span class="line">                q.push(next);</span><br><span class="line">                inq[v] = true;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main() &#123;</span><br><span class="line">    init();</span><br><span class="line">    scanf(&quot;%d%d%d%d%d%d&quot;, &amp;n, &amp;m, &amp;l, &amp;k, &amp;s, &amp;t);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;weight[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    int u, v, w;</span><br><span class="line">    for (int i = 0; i &lt; m; i++) &#123;</span><br><span class="line">        scanf(&quot;%d%d%d&quot;, &amp;u, &amp;v, &amp;w);</span><br><span class="line">        G[u][v] = G[v][u] = w;</span><br><span class="line">    &#125;</span><br><span class="line">    BFS(s);</span><br><span class="line">    if(inq[t] == false)&#123;</span><br><span class="line">        printf(&quot;-1\n&quot;);</span><br><span class="line">        return 0;</span><br><span class="line">    &#125;</span><br><span class="line">    Dijstra(s);</span><br><span class="line">    DFS(t);        //获取最优路径</span><br><span class="line">    printf(&quot;%d %d %d %d\n&quot;, numPath, d[t], remainK, halfSumK);</span><br><span class="line">    for(int i = path.size() - 1; i &gt;= 0; i--) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, path[i]);      //倒着输出路径上的结点</span><br><span class="line">        if(i &gt; 0) printf(&quot;-&gt;&quot;);</span><br><span class="line">        else printf(&quot;\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/4/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/4/">4</a><span class="page-number current">5</span><a class="page-number" href="/page/6/">6</a><span class="space">&hellip;</span><a class="page-number" href="/page/21/">21</a><a class="extend next" rel="next" href="/page/6/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/avatar.jpg" alt="何米酥">
            
              <p class="site-author-name" itemprop="name">何米酥</p>
              <p class="site-description motion-element" itemprop="description">Just do...</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">202</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">78</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/hemisu" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.zhihu.com/people/hemisu" target="_blank" title="知乎">
                      
                        <i class="fa fa-fw fa-globe"></i>知乎</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2015 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">何米酥</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
